package org.chnxi.study.datastructrues.sort;

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSorting {

    public static void main(String[] args) {
        System.out.println("分步执行：");
        int[] arr = {4,6,8,5,9};
        heapSortBystep(arr);

        System.out.println("一步完成：");
        int[] arr2 = {4,6,8,5,9};
        heapSort(arr2);
        System.out.println("排序后："+Arrays.toString(arr2));

        int numCount = 800000;
        System.out.println("测试大量数据的执行耗时["+numCount+"]：");
        int[] randomArr = new int[numCount];
        for (int i =0; i<numCount; i++){
            randomArr[i] = (int) (Math.random()*numCount);
        }

        long start = System.currentTimeMillis();
        int[] randomArrTmp = new int[numCount];
        heapSort(randomArr);
        long end = System.currentTimeMillis();
        System.out.println("执行耗时："+(end - start));
    }

    /**
     * 分步构建大顶堆
     * @param arr
     */
    public static void heapSortBystep(int[] arr){

        //分布完成
        adjustHeap(arr , 1 , arr.length);

        System.out.println("第一次"+Arrays.toString(arr));

        adjustHeap(arr , 0 , arr.length);

        System.out.println("第二次"+Arrays.toString(arr));

    }

    /**
     * 一步完成堆排序
     * @param arr 待排序的数组
     */
    public static void heapSort(int[] arr){
        //将无序序列构成一个堆，根据升序降序需求选择大顶堆或小顶堆
        for (int i = arr.length/2-1; i >= 0; i--){
            adjustHeap(arr , i , arr.length);
        }

        //将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端
        //重新调整结构，使其满足对定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个堆有序
        int tmp = 0;
        for (int j = arr.length - 1; j > 0; j--){
            tmp = arr[j];
            arr[j] = arr[0];
            arr[0] = tmp;
            adjustHeap(arr , 0 , j);
        }
    }

    /**
     * 将数组转换为大顶堆
     * 完成将以i对应的非叶子节点的树，调整为大顶堆
     * 举例：
     *    第一次：int[] arr = {4,6,8,5,9}; i = 1；结果是：{4,9,8,5,6}
     *    第二次：int[] arr = {4,9,8,5,6}; i = 0; 结果是：{9,6,8,5,4}
     * @param arr 待调整的数组
     * @param i 表示非叶子节点在数组中的索引
     * @param len 对多少个元素进行调整，length是在逐渐减少
     */
    public static void adjustHeap(int[] arr , int i , int len){
        //先取出当前变量的值
        int tmp = arr[i];

        //说明：
        // 1. k = i * 2 + 1，k是i节点的左子节点
        for(int k = i*2+1 ; k < len; k = k*2+1){
            if(k+1 < len && arr[k] < arr[k+1]){ //说明左子节点的值小于右子节点的值
                k++; // k指向右子节点
            }

            if(arr[k] > tmp){ //如果子节点大于父节点
                arr[i] = arr[k]; //把较大的值赋给当前节点
                i = k; // i指向k，继续循环比较
            }else{
                break;
            }
        }
        //当for循环结束后，我们已将以i为父节点的子树的最大值，放在了最顶
        //将tmp值放在调整后的位置
        arr[i] = tmp;
    }

}
